package com.hspedu.tree.threadedbinarytree;

/**
 * @author Charlie
 * @version 1.0
 * @date 6/11/2025 下午5:26
 */
public class ThreadedBinaryTreeDemo {
    public static void main(String[] args) {
        HeroNode root = new HeroNode(1, "tom");
        HeroNode node2 = new HeroNode(3, "tom");
        HeroNode node3 = new HeroNode(6, "tom");
        HeroNode node4 = new HeroNode(8, "tom");
        HeroNode node5 = new HeroNode(10, "tom");
        HeroNode node6 = new HeroNode(14, "tom");

        root.setLeft(node2);
        root.setRight(node3);
        node2.setLeft(node4);
        node2.setRight(node5);
        node3.setLeft(node6);

        ThreadedBinaryTree threadedBinaryTree = new ThreadedBinaryTree();
        threadedBinaryTree.setRoot(root);

        threadedBinaryTree.threadNodes();
        HeroNode node5Left = node5.getLeft();
        HeroNode node5Right = node5.getRight();

        System.out.println("node5left=>" + node5Left);
        System.out.println("node5right=>" + node5Right);

         System.out.println("线索化方式遍历");
        threadedBinaryTree.threadList();


    }
}


class ThreadedBinaryTree {
    private HeroNode root;

    //需要创建pre指针，当前结点前驱结点的一个引用
    // 在递归线索化的时候，都保留前驱结点的位置
    private HeroNode pre = null;

    public void setRoot(HeroNode root) {
        this.root = root;
    }

    public void threadNodes(){
        this.threadNodes(root);
    }

    //遍历线索化二叉树的方法
    public void threadList(){
        //定义一个遍历，存储当前遍历的结点。从root开始
        HeroNode node =root;
        while (node!=null){
            //循环找到leftType==1 的结点，第一个找到的就是8
            //后面的node随着遍历会变化，当left=1说明该结点，说明该结点按线索化处理后有效结点
            while (node.getLeftType()==0){
                node=node.getLeft();
            }
            System.out.println(node);
            //当前节点的右边指针是后继结点，就一直输出
            while (node.getRightType()==1){
                //获取当前结点的后继结点
                node=node.getRight();
                System.out.println(node);
            }
            //while循环退出，表示找到的是不是1.替换这个结点
            node=node.getRight();




        }


    }

    //编写对二叉树进行中序线索化方法
    //node 当前需要线索化的结点
    public void threadNodes(HeroNode node) {
        //判断是不是为空
        if (node == null) {
            return;
        }
        // 1  线索化左子树
        threadNodes(node.getLeft());


        // 2  线索化当前节点

        //处理当前结点的前驱结点
        //以8号结点理解， 8结点的left是空
        if (node.getLeft() == null) {
            //当前结点为空，让当前结点的左指针指向前驱结点
            node.setLeft(pre);
            //修改当前左指针的类型, 1是指向前驱结点
            node.setLeftType(1);
        }
        //处理后继结点
        if (pre != null && pre.getRight() == null) {

            //让前驱结点的右指针指向当前节点，修改前驱结点右边指针类型
            pre.setRight(node);
            pre.setRightType(1);
        }

        //！！！每处理完一个结点后，让当前节点是下一个结点的前驱结点
        pre = node;


        // 3  线索化右子树
        threadNodes(node.getRight());

    }


    //删除结点
    public void delNode(int no) {
        if (root != null) {
            //root是不是要删除的结点
            if (root.getNo() == no) {
                root = null;

            } else {
                root.delNode(no);

            }

        } else {
            System.out.println("空树无法删除");
        }

    }

    public void preOrder() {
        if (this.root != null) {
            this.root.preOrder();
        } else {
            System.out.println("当前二叉树为空，无法遍历");
        }
    }

    public void infixOrder() {
        if (this.root != null) {
            this.root.infixOrder();
        } else {
            System.out.println("当前二叉树为空，无法遍历");
        }

    }

    public void postOrder() {
        if (this.root != null) {
            this.root.postOrder();
        } else {
            System.out.println("当前二叉树为空，无法遍历");
        }

    }

    //前序遍历
    public HeroNode preOrderSearch(int no) {
        if (root != null) {
            return root.preOrderSearch(no);
        } else {
            return null;
        }
    }

    //中序遍历
    public HeroNode infixOrderSearch(int no) {
        if (root != null) {
            return root.infixOrderSearch(no);
        } else {
            return null;
        }
    }

    //后序遍历
    public HeroNode postOrderSearch(int no) {
        if (root != null) {
            return root.postOrderSearch(no);
        } else {
            return null;
        }
    }


}

class HeroNode {
    private int no;
    private String name;
    private HeroNode left; //默认为空
    private HeroNode right; // 默认为空


    //1规定 leftType=0 表示指向是左子树，如果是1就是前驱结点
    //2规定 rightType=0表示指向是右子树，如果是1就是后继结点
    private int leftType;
    private int rightType;

    public int getLeftType() {
        return leftType;
    }

    public void setLeftType(int leftType) {
        this.leftType = leftType;
    }

    public int getRightType() {
        return rightType;
    }

    public void setRightType(int rightType) {
        this.rightType = rightType;
    }


    public HeroNode(int no, String name) {
        this.no = no;
        this.name = name;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public HeroNode getLeft() {
        return left;
    }

    public void setLeft(HeroNode left) {
        this.left = left;
    }

    public HeroNode getRight() {
        return right;
    }

    public void setRight(HeroNode right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }

    public void delNode(int no) {


        if (this.left != null && this.left.no == no) {
            this.left = null;
            return;
        }
        if (this.right != null && this.right.no == no) {
            this.right = null;
            return;
        }
        if (this.left != null) {
            this.left.delNode(no);
        }
        if (this.right != null) {
            this.right.delNode(no);
        }


    }

    //编写前序遍历
    public void preOrder() {
        System.out.println(this); //  output the parentNode
        //递归向左子树遍历
        if (this.left != null) {
            this.left.preOrder();
        }
        if (this.right != null) {
            this.right.preOrder();
        }
    }


    public void infixOrder() {
        if (this.left != null) {
            this.left.infixOrder();
        }
        System.out.println(this);
        if (this.right != null) {
            this.right.infixOrder();
        }
    }

    public void postOrder() {
        if (this.left != null) {
            this.left.postOrder();
        }

        if (this.right != null) {
            this.right.postOrder();
        }

        System.out.println(this);

    }

    /*no 雇员编号
     * */
    public HeroNode preOrderSearch(int no) {
        //比较当前节点是不是
        if (this.no == no) {
            return this;
        }
        HeroNode resNode = null;
        if (this.left != null) {
            resNode = this.left.preOrderSearch(no);
        }
        if (resNode != null) { //说明左边找到
            return resNode;
        }

        if (this.right != null) {
            resNode = this.right.preOrderSearch(no);
        }
        if (resNode != null) {
            return resNode;
        }
        return null;

    }


    public HeroNode infixOrderSearch(int no) {

        HeroNode resNode = null;

        if (this.left != null) {
            resNode = this.left.infixOrderSearch(no);
        }
        if (resNode != null) {
            return resNode;
        }
        //
        if (this.no == no) {
            return this;
        }
        if (this.right != null) {
            resNode = this.right.infixOrderSearch(no);
        }
        return resNode;

    }


    public HeroNode postOrderSearch(int no) {
        HeroNode resNode = null;
        if (this.left != null) {
            resNode = this.left.postOrderSearch(no);
        }
        if (resNode != null) {
            return resNode;
        }

        if (this.right != null) {
            resNode = this.right.postOrderSearch(no);
        }
        if (resNode != null) {
            return resNode;
        }
        //如果左右都没有找到，就比较当前节点是不是
        if (this.no == no) {
            return this;
        }
        return resNode;
    }
}




